
'''我们从二叉树的根节点root开始进行深度优先搜索。

在遍历中的每个节点处，我们输出D条短划线（其中D是该节点的深度），然后输出该节点的值。（如果节点的深度为D，则其直接子节点的深度为D + 1。根节点的深度为0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出S，还原树并返回其根节点root。



示例
1：



输入："1-2--3--4-5--6--7"
输出：[1, 2, 5, 3, 4, 6, 7]

示例
2：



输入："1-2--3---4-5--6---7"
输出：[1, 2, 5, 3, null, 6, null, 4, null, 7]

示例
3：



输入："1-401--349---90--88"
输出：[1, 401, null, 349, 88, 90]

提示：


原始树中的节点数介于1和1000之间。每个节点的值介于1和10 ^ 9
'''


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recoverFromPreorder(self, S: str) -> TreeNode:
        ans={-1:TreeNode(0)}
        #利用字典的思想，创建字典存储当前深度的点，根据先序遍历的特性，深度无需长期存储，随用随取
        def AddTree(v,p):
            ans[p]=TreeNode(int(v))#深度为P的节点，其数字为v
            if not ans[p-1].left:#根据先序遍历的特性，深度为p-1的节点，一定是深度为p（两点相邻相邻）的父节点
                ans[p-1].left=ans[p]
            else:
                ans[p-1].right=ans[p]
        val,dep='',0
        for c in S:
            if c !='-':
                val+=c
            elif val:#当前字母为-，前一个字母为数字，可以将前一个数字j添加进树了
                AddTree(val,dep)
                val,dep='',1 #重置val和dep,注意dep重新初始化为1，这是因为当前的字母为-，深度至少为1
            else:#当前字母为-，前一个也为-，连续的-增加深度
                dep+=1
        AddTree(val,dep)#剩余的字母也要添加到树里
        return ans[0]
